/*中缀表达式转换为后缀表达式并求值
把题目给出中缀表达式转换为后缀表达式输出，并求后缀表达式的值。为简单起见，我们约定：
1、输入的中缀表达式一定是合法的，并且只含数字，四种运算符+、-、*、/和小括号；
2、运算数都是一位正整数(1～9)；
3、输入的中缀表达式不超过20个字符；
4、除法运算的结果仍然是正整数。*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SIZE 100

// 定义栈结构
typedef struct sqStack{
    char data[MAX_SIZE]; 
    int top;         
} *Stack;

// 创建并初始化栈
Stack initStack() {
    Stack S = (Stack)malloc(sizeof(struct sqStack));       
    S->top = -1;                                                                     
    return S;
}

// 检查栈是否满
int isFull(Stack S) {
    return S->top == MAX_SIZE - 1;
}

// 检查栈是否空
int isEmpty(Stack S) {
    return S->top == -1;
}

// 入栈操作
void push(Stack S, char value) {
    if (!isFull(S)) {
        S->data[++(S->top)] = value; 
    }
}

// 出栈操作
char pop(Stack S) {
    return isEmpty(S) ? '\0' : S->data[(S->top)--];
}

// 查看栈顶元素
char peek(Stack S) {
    return isEmpty(S) ? '\0' : S->data[S->top]; 
}

// 返回运算符的优先级
int precedence(char op) {
    return (op == '+' || op == '-') ? 1 : (op == '*' || op == '/') ? 2 : 0; // '+'和'-'优先级1，'*'和'/'优先级2
}

// 将中缀表达式转换为后缀表达式
void infixToPostfix(char* infix, char* postfix) {
    Stack S=initStack(S); 
    int j = 0;  

    // 遍历中缀表达式中的每个字符
    for (int i = 0; infix[i]; i++) {
        char c = infix[i];
        if (isdigit(c)) {
            postfix[j++] = c; // 如果是数字，直接添加到后缀表达式中
        } else if (c == '(') {
            push(S, c); // 如果是左括号，压入栈
        } else if (c == ')') {
            // 如果是右括号，弹出栈直到遇到左括号
            while (!isEmpty(S) && peek(S) != '(') {
                postfix[j++] = pop(S);
            }
            pop(S); // 弹出 '('
        } else {
            // 处理运算符
            while (!isEmpty(S) && precedence(peek(S)) >= precedence(c)) {
                postfix[j++] = pop(S); // 弹出栈中优先级大于或等于当前运算符的运算符
            }
            push(S, c); // 将当前运算符压入栈
        }
    }

    // 弹出栈中剩余的运算符
    while (!isEmpty(S)) {
        postfix[j++] = pop(S);
    }
    postfix[j] = '\0'; // 结束后缀表达式
}

// 计算后缀表达式的值
int evaluatePostfix(char* postfix) {
    Stack S=initStack(); 
    // 遍历后缀表达式中的每个字符
    for (int i = 0; postfix[i]; i++) {
        char c = postfix[i];
        if (isdigit(c)) {
            push(S, c - '0'); // 如果是数字，将其转换为整数并压入栈
        } else {
            int b = pop(S), a = pop(S); // 弹出两个操作数
            switch (c) {
                case '+': push(S, a + b); break; 
                case '-': push(S, a - b); break; 
                case '*': push(S, a * b); break; 
                case '/': push(S, a / b); break; 
            }
        }
    }
    return pop(S); 
}

int main() {
    int N;
    scanf("%d\n", &N); 
    char infix[MAX_SIZE], postfix[MAX_SIZE];

    while (N--) {
        fgets(infix, sizeof(infix), stdin); // 读取中缀表达式
        infix[strcspn(infix, "\n")] = 0; // 去除换行符
        infixToPostfix(infix, postfix); // 转换为后缀表达式
        printf("%s %d\n", postfix, evaluatePostfix(postfix)); // 打印后缀表达式及其计算结果
    }

    return 0; 
}